package com.leetcodehot.problems;

import java.util.Arrays;

public class problems2466 {
    private int res = 0;
    private int[] memo;
    private final int MOD = (int) (Math.pow(10, 9) + 7);

    public int countGoodStrings(int low, int high, int zero, int one) {
        memo = new int[high + 1];
        Arrays.fill(memo, -1);
        dfs(0, low, high, zero, one);

        return res;
    }

    private void dfs(int len, int low, int high, int zero, int one) {
        if (len > high) return;
        if (low <= len && len <= high) {
            res = (res + 1) % MOD;
        }
        if (memo[len] != -1) {
            res = (res + memo[len]) % MOD;
            return;
        }

        int temp = res;
        if (len + zero <= high) {
            dfs(len + zero, low, high, zero, one);
        }
        if (len + one <= high) {
            dfs(len + one, low, high, zero, one);
        }
        memo[len] = (res - temp + MOD) % MOD;
    }
}
